home *** CD-ROM | disk | FTP | other *** search
/ Sprite 1984 - 1993 / Sprite 1984 - 1993.iso / src / lib / c / etc / ndbm.c < prev    next >
Encoding:
C/C++ Source or Header  |  1989-07-22  |  10.6 KB  |  538 lines
  1. /*
  2.  * Copyright (c) 1983 Regents of the University of California.
  3.  * All rights reserved.  The Berkeley software License Agreement
  4.  * specifies the terms and conditions for redistribution.
  5.  */
  6.  
  7. #if defined(LIBC_SCCS) && !defined(lint)
  8. static char sccsid[] = "@(#)ndbm.c    5.4 (Berkeley) 9/4/87";
  9. #endif LIBC_SCCS and not lint
  10.  
  11. #include <sys/types.h>
  12. #include <sys/stat.h>
  13. #include <sys/file.h>
  14. #include <stdio.h>
  15. #include <errno.h>
  16. #include <ndbm.h>
  17. #include <stdlib.h>
  18. #include <string.h>
  19.  
  20. #define BYTESIZ 8
  21. #undef setbit
  22.  
  23. static  datum makdatum();
  24. static  long dcalchash();
  25. static  int dbm_access();
  26. static  int getbit();
  27. static  int setbit();
  28. static  int finddatum();
  29. static  int delitem();
  30. static  int additem();
  31.  
  32. extern  int errno;
  33. extern    long lseek();
  34.  
  35.     /* VARARGS2 */
  36. DBM *
  37. dbm_open(file, flags, mode)
  38.     char *file;
  39.     int flags, mode;
  40. {
  41.     struct stat statb;
  42.     register DBM *db;
  43.  
  44.     if ((db = (DBM *)malloc(sizeof *db)) == 0) {
  45.         errno = ENOMEM;
  46.         return ((DBM *)0);
  47.     }
  48.     db->dbm_flags = (flags & 03) == O_RDONLY ? _DBM_RDONLY : 0;
  49.     if ((flags & 03) == O_WRONLY)
  50.         flags = (flags & ~03) | O_RDWR;
  51.     strcpy(db->dbm_pagbuf, file);
  52.     strcat(db->dbm_pagbuf, ".pag");
  53.     db->dbm_pagf = open(db->dbm_pagbuf, flags, mode);
  54.     if (db->dbm_pagf < 0)
  55.         goto bad;
  56.     strcpy(db->dbm_pagbuf, file);
  57.     strcat(db->dbm_pagbuf, ".dir");
  58.     db->dbm_dirf = open(db->dbm_pagbuf, flags, mode);
  59.     if (db->dbm_dirf < 0)
  60.         goto bad1;
  61.     fstat(db->dbm_dirf, &statb);
  62.     db->dbm_maxbno = statb.st_size*BYTESIZ-1;
  63.     db->dbm_pagbno = db->dbm_dirbno = -1;
  64.     return (db);
  65. bad1:
  66.     (void) close(db->dbm_pagf);
  67. bad:
  68.     free((char *)db);
  69.     return ((DBM *)0);
  70. }
  71.  
  72. void
  73. dbm_close(db)
  74.     DBM *db;
  75. {
  76.  
  77.     (void) close(db->dbm_dirf);
  78.     (void) close(db->dbm_pagf);
  79.     free((char *)db);
  80. }
  81.  
  82. long
  83. dbm_forder(db, key)
  84.     register DBM *db;
  85.     datum key;
  86. {
  87.     long hash;
  88.  
  89.     hash = dcalchash(key);
  90.     for (db->dbm_hmask=0;; db->dbm_hmask=(db->dbm_hmask<<1)+1) {
  91.         db->dbm_blkno = hash & db->dbm_hmask;
  92.         db->dbm_bitno = db->dbm_blkno + db->dbm_hmask;
  93.         if (getbit(db) == 0)
  94.             break;
  95.     }
  96.     return (db->dbm_blkno);
  97. }
  98.  
  99. datum
  100. dbm_fetch(db, key)
  101.     register DBM *db;
  102.     datum key;
  103. {
  104.     register i;
  105.     datum item;
  106.  
  107.     if (dbm_error(db))
  108.         goto err;
  109.     dbm_access(db, dcalchash(key));
  110.     if ((i = finddatum(db->dbm_pagbuf, key)) >= 0) {
  111.         item = makdatum(db->dbm_pagbuf, i+1);
  112.         if (item.dptr != NULL)
  113.             return (item);
  114.     }
  115. err:
  116.     item.dptr = NULL;
  117.     item.dsize = 0;
  118.     return (item);
  119. }
  120.  
  121. dbm_delete(db, key)
  122.     register DBM *db;
  123.     datum key;
  124. {
  125.     register i;
  126.  
  127.     if (dbm_error(db))
  128.         return (-1);
  129.     if (dbm_rdonly(db)) {
  130.         errno = EPERM;
  131.         return (-1);
  132.     }
  133.     dbm_access(db, dcalchash(key));
  134.     if ((i = finddatum(db->dbm_pagbuf, key)) < 0)
  135.         return (-1);
  136.     if (!delitem(db->dbm_pagbuf, i))
  137.         goto err;
  138.     db->dbm_pagbno = db->dbm_blkno;
  139.     (void) lseek(db->dbm_pagf, db->dbm_blkno*PBLKSIZ, L_SET);
  140.     if (write(db->dbm_pagf, db->dbm_pagbuf, PBLKSIZ) != PBLKSIZ) {
  141.     err:
  142.         db->dbm_flags |= _DBM_IOERR;
  143.         return (-1);
  144.     }
  145.     return (0);
  146. }
  147.  
  148. dbm_store(db, key, dat, replace)
  149.     register DBM *db;
  150.     datum key, dat;
  151.     int replace;
  152. {
  153.     register i;
  154.     datum item, item1;
  155.     char ovfbuf[PBLKSIZ];
  156.  
  157.     if (dbm_error(db))
  158.         return (-1);
  159.     if (dbm_rdonly(db)) {
  160.         errno = EPERM;
  161.         return (-1);
  162.     }
  163. loop:
  164.     dbm_access(db, dcalchash(key));
  165.     if ((i = finddatum(db->dbm_pagbuf, key)) >= 0) {
  166.         if (!replace)
  167.             return (1);
  168.         if (!delitem(db->dbm_pagbuf, i)) {
  169.             db->dbm_flags |= _DBM_IOERR;
  170.             return (-1);
  171.         }
  172.     }
  173.     if (!additem(db->dbm_pagbuf, key, dat))
  174.         goto split;
  175.     db->dbm_pagbno = db->dbm_blkno;
  176.     (void) lseek(db->dbm_pagf, db->dbm_blkno*PBLKSIZ, L_SET);
  177.     if (write(db->dbm_pagf, db->dbm_pagbuf, PBLKSIZ) != PBLKSIZ) {
  178.         db->dbm_flags |= _DBM_IOERR;
  179.         return (-1);
  180.     }
  181.     return (0);
  182.  
  183. split:
  184.     if (key.dsize+dat.dsize+3*sizeof(short) >= PBLKSIZ) {
  185.         db->dbm_flags |= _DBM_IOERR;
  186.         errno = ENOSPC;
  187.         return (-1);
  188.     }
  189.     bzero(ovfbuf, PBLKSIZ);
  190.     for (i=0;;) {
  191.         item = makdatum(db->dbm_pagbuf, i);
  192.         if (item.dptr == NULL)
  193.             break;
  194.         if (dcalchash(item) & (db->dbm_hmask+1)) {
  195.             item1 = makdatum(db->dbm_pagbuf, i+1);
  196.             if (item1.dptr == NULL) {
  197.                 fprintf(stderr, "ndbm: split not paired\n");
  198.                 db->dbm_flags |= _DBM_IOERR;
  199.                 break;
  200.             }
  201.             if (!additem(ovfbuf, item, item1) ||
  202.                 !delitem(db->dbm_pagbuf, i)) {
  203.                 db->dbm_flags |= _DBM_IOERR;
  204.                 return (-1);
  205.             }
  206.             continue;
  207.         }
  208.         i += 2;
  209.     }
  210.     db->dbm_pagbno = db->dbm_blkno;
  211.     (void) lseek(db->dbm_pagf, db->dbm_blkno*PBLKSIZ, L_SET);
  212.     if (write(db->dbm_pagf, db->dbm_pagbuf, PBLKSIZ) != PBLKSIZ) {
  213.         db->dbm_flags |= _DBM_IOERR;
  214.         return (-1);
  215.     }
  216.     (void) lseek(db->dbm_pagf, (db->dbm_blkno+db->dbm_hmask+1)*PBLKSIZ, L_SET);
  217.     if (write(db->dbm_pagf, ovfbuf, PBLKSIZ) != PBLKSIZ) {
  218.         db->dbm_flags |= _DBM_IOERR;
  219.         return (-1);
  220.     }
  221.     setbit(db);
  222.     goto loop;
  223. }
  224.  
  225. datum
  226. dbm_firstkey(db)
  227.     DBM *db;
  228. {
  229.  
  230.     db->dbm_blkptr = 0L;
  231.     db->dbm_keyptr = 0;
  232.     return (dbm_nextkey(db));
  233. }
  234.  
  235. datum
  236. dbm_nextkey(db)
  237.     register DBM *db;
  238. {
  239.     struct stat statb;
  240.     datum item;
  241.  
  242.     if (dbm_error(db) || fstat(db->dbm_pagf, &statb) < 0)
  243.         goto err;
  244.     statb.st_size /= PBLKSIZ;
  245.     for (;;) {
  246.         if (db->dbm_blkptr != db->dbm_pagbno) {
  247.             db->dbm_pagbno = db->dbm_blkptr;
  248.             (void) lseek(db->dbm_pagf, db->dbm_blkptr*PBLKSIZ, L_SET);
  249.             if (read(db->dbm_pagf, db->dbm_pagbuf, PBLKSIZ) != PBLKSIZ)
  250.                 bzero(db->dbm_pagbuf, PBLKSIZ);
  251. #ifdef DEBUG
  252.             else if (chkblk(db->dbm_pagbuf) < 0)
  253.                 db->dbm_flags |= _DBM_IOERR;
  254. #endif
  255.         }
  256.         if (((short *)db->dbm_pagbuf)[0] != 0) {
  257.             item = makdatum(db->dbm_pagbuf, db->dbm_keyptr);
  258.             if (item.dptr != NULL) {
  259.                 db->dbm_keyptr += 2;
  260.                 return (item);
  261.             }
  262.             db->dbm_keyptr = 0;
  263.         }
  264.         if (++db->dbm_blkptr >= statb.st_size)
  265.             break;
  266.     }
  267. err:
  268.     item.dptr = NULL;
  269.     item.dsize = 0;
  270.     return (item);
  271. }
  272.  
  273. static
  274. dbm_access(db, hash)
  275.     register DBM *db;
  276.     long hash;
  277. {
  278.  
  279.     for (db->dbm_hmask=0;; db->dbm_hmask=(db->dbm_hmask<<1)+1) {
  280.         db->dbm_blkno = hash & db->dbm_hmask;
  281.         db->dbm_bitno = db->dbm_blkno + db->dbm_hmask;
  282.         if (getbit(db) == 0)
  283.             break;
  284.     }
  285.     if (db->dbm_blkno != db->dbm_pagbno) {
  286.         db->dbm_pagbno = db->dbm_blkno;
  287.         (void) lseek(db->dbm_pagf, db->dbm_blkno*PBLKSIZ, L_SET);
  288.         if (read(db->dbm_pagf, db->dbm_pagbuf, PBLKSIZ) != PBLKSIZ)
  289.             bzero(db->dbm_pagbuf, PBLKSIZ);
  290. #ifdef DEBUG
  291.         else if (chkblk(db->dbm_pagbuf) < 0)
  292.             db->dbm_flags |= _DBM_IOERR;
  293. #endif
  294.     }
  295. }
  296.  
  297. static
  298. getbit(db)
  299.     register DBM *db;
  300. {
  301.     long bn;
  302.     register b, i, n;
  303.     
  304.  
  305.     if (db->dbm_bitno > db->dbm_maxbno)
  306.         return (0);
  307.     n = db->dbm_bitno % BYTESIZ;
  308.     bn = db->dbm_bitno / BYTESIZ;
  309.     i = bn % DBLKSIZ;
  310.     b = bn / DBLKSIZ;
  311.     if (b != db->dbm_dirbno) {
  312.         db->dbm_dirbno = b;
  313.         (void) lseek(db->dbm_dirf, (long)b*DBLKSIZ, L_SET);
  314.         if (read(db->dbm_dirf, db->dbm_dirbuf, DBLKSIZ) != DBLKSIZ)
  315.             bzero(db->dbm_dirbuf, DBLKSIZ);
  316.     }
  317.     return (db->dbm_dirbuf[i] & (1<<n));
  318. }
  319.  
  320. static
  321. setbit(db)
  322.     register DBM *db;
  323. {
  324.     long bn;
  325.     register i, n, b;
  326.  
  327.     if (db->dbm_bitno > db->dbm_maxbno)
  328.         db->dbm_maxbno = db->dbm_bitno;
  329.     n = db->dbm_bitno % BYTESIZ;
  330.     bn = db->dbm_bitno / BYTESIZ;
  331.     i = bn % DBLKSIZ;
  332.     b = bn / DBLKSIZ;
  333.     if (b != db->dbm_dirbno) {
  334.         db->dbm_dirbno = b;
  335.         (void) lseek(db->dbm_dirf, (long)b*DBLKSIZ, L_SET);
  336.         if (read(db->dbm_dirf, db->dbm_dirbuf, DBLKSIZ) != DBLKSIZ)
  337.             bzero(db->dbm_dirbuf, DBLKSIZ);
  338.     }
  339.     db->dbm_dirbuf[i] |= 1<<n;
  340.     db->dbm_dirbno = b;
  341.     (void) lseek(db->dbm_dirf, (long)b*DBLKSIZ, L_SET);
  342.     if (write(db->dbm_dirf, db->dbm_dirbuf, DBLKSIZ) != DBLKSIZ)
  343.         db->dbm_flags |= _DBM_IOERR;
  344. }
  345.  
  346. static datum
  347. makdatum(buf, n)
  348.     char buf[PBLKSIZ];
  349. {
  350.     register short *sp;
  351.     register t;
  352.     datum item;
  353.  
  354.     sp = (short *)buf;
  355.     if ((unsigned)n >= sp[0]) {
  356.         item.dptr = NULL;
  357.         item.dsize = 0;
  358.         return (item);
  359.     }
  360.     t = PBLKSIZ;
  361.     if (n > 0)
  362.         t = sp[n];
  363.     item.dptr = buf+sp[n+1];
  364.     item.dsize = t - sp[n+1];
  365.     return (item);
  366. }
  367.  
  368. static
  369. finddatum(buf, item)
  370.     char buf[PBLKSIZ];
  371.     datum item;
  372. {
  373.     register short *sp;
  374.     register int i, n, j;
  375.  
  376.     sp = (short *)buf;
  377.     n = PBLKSIZ;
  378.     for (i=0, j=sp[0]; i<j; i+=2, n = sp[i]) {
  379.         n -= sp[i+1];
  380.         if (n != item.dsize)
  381.             continue;
  382.         if (n == 0 || bcmp(&buf[sp[i+1]], item.dptr, n) == 0)
  383.             return (i);
  384.     }
  385.     return (-1);
  386. }
  387.  
  388. static  int hitab[16]
  389. /* ken's
  390. {
  391.     055,043,036,054,063,014,004,005,
  392.     010,064,077,000,035,027,025,071,
  393. };
  394. */
  395.  = {    61, 57, 53, 49, 45, 41, 37, 33,
  396.     29, 25, 21, 17, 13,  9,  5,  1,
  397. };
  398. static  long hltab[64]
  399.  = {
  400.     06100151277L,06106161736L,06452611562L,05001724107L,
  401.     02614772546L,04120731531L,04665262210L,07347467531L,
  402.     06735253126L,06042345173L,03072226605L,01464164730L,
  403.     03247435524L,07652510057L,01546775256L,05714532133L,
  404.     06173260402L,07517101630L,02431460343L,01743245566L,
  405.     00261675137L,02433103631L,03421772437L,04447707466L,
  406.     04435620103L,03757017115L,03641531772L,06767633246L,
  407.     02673230344L,00260612216L,04133454451L,00615531516L,
  408.     06137717526L,02574116560L,02304023373L,07061702261L,
  409.     05153031405L,05322056705L,07401116734L,06552375715L,
  410.     06165233473L,05311063631L,01212221723L,01052267235L,
  411.     06000615237L,01075222665L,06330216006L,04402355630L,
  412.     01451177262L,02000133436L,06025467062L,07121076461L,
  413.     03123433522L,01010635225L,01716177066L,05161746527L,
  414.     01736635071L,06243505026L,03637211610L,01756474365L,
  415.     04723077174L,03642763134L,05750130273L,03655541561L,
  416. };
  417.  
  418. static long
  419. hashinc(db, hash)
  420.     register DBM *db;
  421.     long hash;
  422. {
  423.     long bit;
  424.  
  425.     hash &= db->dbm_hmask;
  426.     bit = db->dbm_hmask+1;
  427.     for (;;) {
  428.         bit >>= 1;
  429.         if (bit == 0)
  430.             return (0L);
  431.         if ((hash & bit) == 0)
  432.             return (hash | bit);
  433.         hash &= ~bit;
  434.     }
  435. }
  436.  
  437. static long
  438. dcalchash(item)
  439.     datum item;
  440. {
  441.     register int s, c, j;
  442.     register char *cp;
  443.     register long hashl;
  444.     register int hashi;
  445.  
  446.     hashl = 0;
  447.     hashi = 0;
  448.     for (cp = item.dptr, s=item.dsize; --s >= 0; ) {
  449.         c = *cp++;
  450.         for (j=0; j<BYTESIZ; j+=4) {
  451.             hashi += hitab[c&017];
  452.             hashl += hltab[hashi&63];
  453.             c >>= 4;
  454.         }
  455.     }
  456.     return (hashl);
  457. }
  458.  
  459. /*
  460.  * Delete pairs of items (n & n+1).
  461.  */
  462. static
  463. delitem(buf, n)
  464.     char buf[PBLKSIZ];
  465. {
  466.     register short *sp, *sp1;
  467.     register i1, i2;
  468.  
  469.     sp = (short *)buf;
  470.     i2 = sp[0];
  471.     if ((unsigned)n >= i2 || (n & 1))
  472.         return (0);
  473.     if (n == i2-2) {
  474.         sp[0] -= 2;
  475.         return (1);
  476.     }
  477.     i1 = PBLKSIZ;
  478.     if (n > 0)
  479.         i1 = sp[n];
  480.     i1 -= sp[n+2];
  481.     if (i1 > 0) {
  482.         i2 = sp[i2];
  483.         bcopy(&buf[i2], &buf[i2 + i1], sp[n+2] - i2);
  484.     }
  485.     sp[0] -= 2;
  486.     for (sp1 = sp + sp[0], sp += n+1; sp <= sp1; sp++)
  487.         sp[0] = sp[2] + i1;
  488.     return (1);
  489. }
  490.  
  491. /*
  492.  * Add pairs of items (item & item1).
  493.  */
  494. static
  495. additem(buf, item, item1)
  496.     char buf[PBLKSIZ];
  497.     datum item, item1;
  498. {
  499.     register short *sp;
  500.     register i1, i2;
  501.  
  502.     sp = (short *)buf;
  503.     i1 = PBLKSIZ;
  504.     i2 = sp[0];
  505.     if (i2 > 0)
  506.         i1 = sp[i2];
  507.     i1 -= item.dsize + item1.dsize;
  508.     if (i1 <= (i2+3) * (int)sizeof(short))
  509.         return (0);
  510.     sp[0] += 2;
  511.     sp[++i2] = i1 + item1.dsize;
  512.     bcopy(item.dptr, &buf[i1 + item1.dsize], item.dsize);
  513.     sp[++i2] = i1;
  514.     bcopy(item1.dptr, &buf[i1], item1.dsize);
  515.     return (1);
  516. }
  517.  
  518. #ifdef DEBUG
  519. static
  520. chkblk(buf)
  521.     char buf[PBLKSIZ];
  522. {
  523.     register short *sp;
  524.     register t, i;
  525.  
  526.     sp = (short *)buf;
  527.     t = PBLKSIZ;
  528.     for (i=0; i<sp[0]; i++) {
  529.         if (sp[i+1] > t)
  530.             return (-1);
  531.         t = sp[i+1];
  532.     }
  533.     if (t < (sp[0]+1)*sizeof(short))
  534.         return (-1);
  535.     return (0);
  536. }
  537. #endif
  538.